package org.cainiao.algorithm.temp.niuke;

import java.io.IOException;
import java.util.Scanner;

/**
 * <br />
 * <p>
 * Author: Cai Niao(wdhlzd@163.com)<br />
 */
public class HJ61 {

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            System.out.println(countDP(in.nextInt(), in.nextInt()));
        }
    }

    /**
     * -       0 1 2 3... n
     * <p>
     * 0       1 1 1 1... 1
     * 1       1 1 1 1... 1
     * 2       0 1 0 0... 0
     * ...     ...
     * m       0 1 0 0... 0
     */
    private static int countDP(int m, int n) {
        if (m == 0 || m == 1 || n == 1) {
            return 1;
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            dp[0][i] = 1;
            dp[1][i] = 1;
        }
        for (int i = 0; i <= m; i++) {
            dp[i][1] = 1;
        }
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = i < j ? dp[i][i] : dp[i - j][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    /**
     * 苹果放置完成后，n 个盘子形成一个 n 维数组，数组的元素值为盘子中的苹果数
     * 所有的放置方法，会形成一个数组集合
     * 对集合中的每个数组按元素大小排序，然后将数组低位索引到高位索引的值，形成一个 m 进制数
     * 对 m 进制数去重后，m 进制数的数量就是题目所求的方案数
     */
    private static int count(int m, int n) {
        if (m == 0 || m == 1 || n == 1) {
            /*
             * 如果没有苹果了，则只有一种放置方法，即所有盘子都不放，返回 1
             * 如果只有一个苹果，无论这个苹果放到哪个盘子中，根据题目，都属于同一种放置方法，返回 1
             * 如果只有一个盘子，则只有一种放置方法，即所有苹果都放到这个盘子中，返回 1
             */
            return 1;
        }
        if (m < n) {
            /*
             * 苹果数少于盘子数量，最终的 m 进制数中，高 m - n 位都为 0
             * 去掉所有 m 进制数中的高 m - n 位，不会影响排列组合的数量，即不会影响基数
             * 也就是说，方案数与 m 个苹果 m 个盘子的情况相同
             * 例如：
             * 2 个苹果，4 个盘子：0011、0002
             * 2 个苹果，2 个盘子：11、02
             */
            return count(m, m);
        }
        /*
         * 到这里，说明苹果数量不少于盘子数量，也就是说，一定存在每个盘子都有苹果的分法
         * 为了缩小递归规模，将可能的分法拆分为了两种互斥的情况，然后分类相加计数：
         * 1）每个盘子中都有苹果的情况，有多少种放法
         *     方案数为 count(m - n, n)
         *     即，先在每个盘子里放一个苹果之后，就只剩下 m - n 个苹果了
         *     将这剩下的 m - n 个苹果放到 n 个盘子，有 count(m - n, n) 种放法
         * 2）至少有一个盘子中没有苹果
         *     方案数为 count(m, n - 1)
         */
        return count(m - n, n) + count(m, n - 1);
    }
}
